package com.github.tangmonkmeat;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Description:
 * 某风电场每台风机的发电量和距离升压站的距离各不相同，
 * 如：
 * 风机1：发电量30，距离20；
 * 风机2：发电量35，距离25；
 * 风机3：发电量25，距离18……，
 * <p>
 * 要求在输电总距离限定（如小于100）的前提下，选择风机向升压站输电，使得输送的电量最大。
 *
 * @author zwl
 * @version 1.0
 * @date 2021/3/12 下午2:57
 */
public class 风机向升压站输电 {

    public static void main(String[] args){
        //Scanner scanner = new Scanner(System.in);
        //String s1 = scanner.nextLine();
        //String s2 = scanner.nextLine();
        //int k = scanner.nextInt();
        //scanner.close();
        //int result = getMaxEle3(s2i(s1),s2i(s2),k);
        //System.out.println(result);

        int res = getMaxEle3(new int[]{20, 30, 35, 40},
                             new int[]{18, 20, 25, 30},
                            60);
        System.out.println(res);
    }

    public static int[] s2i(String s){
        String[] sp = s.split(" ");
        int[] res = new int[sp.length];
        for(int i = 0;i < res.length;i++){
            res[i] = Integer.parseInt(sp[i]);
        }
        return res;
    }

    // 01背包问题？
    // len[] 重量 30 20 35 40
    // ele[] 价值 20 18 25 30
    // k 背包的限制容量 60
    public static int getMaxEle3(int[] len, int[] ele, int maxLen) {
        int[] a = new int[len.length + 1];
        System.arraycopy(len,0,a,1,len.length);
        int[] b = new int[ele.length + 1];
        System.arraycopy(ele,0,b,1,ele.length);
        int[][] dp= new int[len.length + 1][maxLen + 1];
        
        for(int i = 1;i < a.length;i++){
            for(int j = 1;j <= maxLen;j++){
                if(j >= a[i]){
                    // 两种可能
                    // 1 不放物品 i
                    // 2 放物品 i, 但是必须腾出空间
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - a[i]] + b[i]);
                }else{
                    // 当前容量,完全放不下物品i
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[a.length - 1][maxLen];
    }

    public static int getMaxEle(int[] ele, int[] len, int maxLen) {
        int maxEle = 0;
        if (maxLen > 0) {
            for (int i = 0; i < ele.length; i++) {
                int curEle;
                int l = len[i];
                int e = ele[i];
                if (l <= maxLen) {
                    curEle = getMaxEle(ele, len, maxLen - l) + e;
                    if (curEle > maxEle) {
                        maxEle = curEle;
                    }
                }
            }
        }
        return maxEle;
    }

    public static int getMaxEle2(int[] ele, int[] len, int maxLen) {
        int[][] ps = new int[maxLen][maxLen + 1];
        for (int i = 1; i < ele.length; i++) {
            for (int v = 1; v < maxLen; v++) {
                // 存的下
                int with = (v - len[i] >= 0) ? (ele[i - 1] + ele[v - len[i - 1]]) : 0;
                // 存不下
                int without = ele[i - 1];
                // 存最大值
                ps[i][v] = Math.max(with,without);
            }
        }
        return ps[maxLen - 1][maxLen];
    }
}
